/*
 * [22] 删除链表倒数第k个节点
 * 
 * Given linked list: 1->2->3->4->5, and n = 2.
 * After removing the second node from the end, the linked list becomes 1->2->3->5.
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

// 回顾普通的二分查找
/**
int binarysearch(vector<int>& a, int k) {
  int left = 0;
  int right = a.size() - 1;
  int mid;
  while (left <= right) {
    mid = (left + right) / 2;
    // k较a[mid]大时，在右半区间查找
    if (a[mid] < k) left = mid + 1;
    // k较a[mid]小时，在右半区间查找
    else if (a[mid] > k)
      right = mid - 1;
    // 若相等则返回mid
    else
      return mid;
  }
  // 找不到时返回-1
  return -1；
}
**/

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

// Definition for singly-linked list.
struct ListNode
{
  int val;
  struct ListNode *pnext;
  ListNode(int x) : val(x), pnext(NULL)
  {
  }
};

class Solution
{
public:
  ListNode *removeNthFromEnd(ListNode *pHead, int n)
  {
    // 防御性编程
    if (pHead == nullptr || n == 0)
      return pHead;
    // 创建头结点，方便处理只有一个结点或者移除首结点的特殊情况
    ListNode prehead(0);
    // 指向首结点
    prehead.pnext = pHead;
    ListNode *fast = &prehead, *slow = &prehead;

    // fast领先n+1步,循环退出时，fast在位置n+1,slow在位置0(prehead位置为0
    for (int i = 0; i <= n + 1; i++)
    {
      fast = fast->pnext;
    }
    // 同时移动fast和slow直到fast到尾部哨兵
    while (fast != nullptr)
    {
      // 结果为fast指向最后一个结点之后为nullptr,slow指向倒数第（n+1）个结点
      //（找到倒数第n+1个结点，方便删除下一个结点）
      fast = fast->pnext;
      slow = slow->pnext;
    }
    // 倒数第n个结点
    ListNode *temp = slow->pnext;
    // 跳过倒数第n个结点
    // 从语义理解等式左边的slow->pnext为slow当前节点的指针域
    slow->pnext = slow->pnext->pnext;

    delete temp;
    temp = nullptr;

    return prehead.pnext;
  }
};

int main()
{
  class Solution solute;
  ListNode *nodehead = new ListNode(-1);

  ListNode *node1 = new ListNode(1);
  nodehead->pnext = node1;

  ListNode *node2 = new ListNode(2);
  node1->pnext = node2;
  node2->pnext = nullptr;

  ListNode *node3 = new ListNode(2);
  node2->pnext = node3;
  node3->pnext = nullptr;

  ListNode *node4 = new ListNode(3);
  node3->pnext = node4;
  node4->pnext = nullptr;

  ListNode *head = solute.removeNthFromEnd(node1);

  return 0;
}

// @lc code=end
